import numpy as np


class Task13:
    def run(self, m, n, k):
        visited = np.zeros((m, n))
        return self.count(visited, m, n, k, 0, 0)

    def count(self, visited, m, n, k, row, col):
        if row < 0 or row >= m or col < 0 or col >= n or visited[row][col]:
            return 0
        if self.sum_digits(row) + self.sum_digits(col) > k:
            return 0
        count = 1
        visited[row][col] = 1
        count += self.count(visited, m, n, k, row + 1, col)
        count += self.count(visited, m, n, k, row, col + 1)
        count += self.count(visited, m, n, k, row - 1, col)
        count += self.count(visited, m, n, k, row, col - 1)
        return count

    def sum_digits(self, num):
        sum = 0
        while num > 0:
            sum += num % 10
            num = num // 10
        return sum
